import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 沈明月
 * Date: 2022-11-02
 * Time: 21:52
 */
public class KnowledgeThree {
//递归：把原问题分解成小问题，小问题的解决方式和大问题的一样
//自己调用自己，有一个起始条件（终止条件）
//难在如何确定递归公式
//递归求n!：
    public static int fac(int n){
        if(n == 1){
            return 1;
        }else{
            return n*fac(n-1);
        }
    }
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //输入想要得到的数的阶乘:
        int n = scanner.nextInt();
        int ret = fac(n);
        System.out.println("n!是"+ret);
    }


//递归练习：
//按顺序打印数字的每一位（正序）：
    public static void func1(int n){
        if(n <=9){
            System.out.println(n%10);
            return ;
        }
        func1(n/10);
        System.out.println(n%10);
    }
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        func1(n);
    }

//递归求1+2+3+……+10=
    public static int sum(int n){
        if(n == 1){
            return 1;
        }
        return n+sum(n-1);
    }
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(sum(n));
    }

//求一个数的各个位上的数字的和：
    public static int func2(int n){
        if(n <= 9){
            return n;
        }return n%10+func2(n/10);
    }
    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(func2(n));
    }

//汉诺塔（也称河内塔）问题：
    public static  void hannuota(int n,char pos1,char pos2,char pos3){
    if (n == 1){
            move(pos1,pos3);
            return;
        }
        hannuota(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hannuota(n-1,pos2,pos1,pos3);
    }
    public static void move(char pos1,char pos2){
        System.out.print(pos1+"->"+pos2+" ");
    }
    public static void main(String[] args) {
        hannuota(3,'A','B','C');
    }
}
